A Novel Parser Design Algorithm Based on Artificial Ants

摘要

This article presents a unique design for a parser using the Ant ColonyOptimization algorithm. The paper implements the intuitive thought process ofhuman mind through the activities of artificial ants. The scheme presented hereuses a bottom-up approach and the parsing program can directly use ambiguous orredundant grammars. We allocate a node corresponding to each production rulepresent in the given grammar. Each node is connected to all other nodes(representing other production rules), thereby establishing a completelyconnected graph susceptible to the movement of artificial ants. Each ant triesto modify this sentential form by the production rule present in the node andupgrades its position until the sentential form reduces to the start symbol S.Successful ants deposit pheromone on the links that they have traversedthrough. Eventually, the optimum path is discovered by the links carryingmaximum amount of pheromone concentration. The design is simple, versatile,robust and effective and obviates the calculation of the above mentioned setsand precedence relation tables. Further advantages of our scheme lie in i)ascertaining whether a given string belongs to the language represented by thegrammar, and ii) finding out the shortest possible path from the given stringto the start symbol S in case multiple routes exist.